// CSc 522, hw1
// sequential version of red/black grid computation
//Jinyan Huan (jguan1@email.arizona.edu) & Fengqiong Huang (huangfq@emailo.arizona.edu)

#include <stdio.h>
#include <sys/types.h>
#include <stdlib.h>
#include <sys/time.h>

int num_iters;
int grid_size;
double start_time;
double end_time;
struct timeval timer;

void print_grid(double **mat) {
	int i, j;

	printf("The %d * %d grid is\n", grid_size, grid_size);
	for (i = 0; i <= grid_size + 1; i++) {
		for (j = 0; j <= grid_size + 1; j++) {
			printf("%lf ", mat[i][j]);
		}
		printf("\n");
	}
}

int main(int argc, char** argv) {
	int i, j, n, j_start;
	double *vals;
	double **grid;
	double temp, old_val;
	double max_diff;
	const long UNITS = 1000000;

	//validate arguments count
	if (argc != 3) {
		printf("Usuage: %s <grid-size> <num-iterations>\n", argv[0]);
		exit(1);
	}

	//read program arguments
	grid_size = atoi(argv[1]);
	num_iters = atoi(argv[2]);

	//validate program arguments
	if (grid_size <= 0 || grid_size % 8 != 0) {
		printf("Invalid grid_size: grid_size should be a multiple of 8");
		exit(1);
	}
	if (num_iters <= 0) {
		printf("Invalid num_iters: num_iters should be positive integer.");
		exit(1);
	}

	// allocate values
	vals
			= (double *) malloc((grid_size + 2) * (grid_size + 2)
					* sizeof(double));
	// allocate vector of pointers
	grid = (double **) malloc((grid_size + 2) * sizeof(double*));
	for (i = 0; i < grid_size + 2; i++) {
		grid[i] = &(vals[i * (grid_size + 2)]);
	}

	// Initialize the grid
	for (i = 1; i < grid_size + 1; i++) {
		for (j = 1; j < grid_size + 1; j++) {
			grid[i][j] = 0.0;
		}
	}

	// borders
	for (j = 0; j < grid_size + 2; j++) {
		grid[0][j] = 1.0;
		grid[grid_size + 1][j] = 1.0;
	}
	for (i = 0; i < grid_size + 2; i++) {
		grid[i][0] = 1.0;
		grid[i][grid_size + 1] = 1.0;
	}

	gettimeofday(&timer, NULL);
    start_time = timer.tv_sec + (timer.tv_usec/1000000.0); 

	// Performing sequential red-black grid computation
	for (n = 0; n < num_iters - 1; n++) {
		// update red points
		for (i = 1; i <= grid_size; i++) {
			if (i % 2 == 1)
				j_start = 1;
			else
				j_start = 2;
			for (j = j_start; j <= grid_size; j = j + 2) {
				grid[i][j] = (grid[i - 1][j] + grid[i][j - 1] + grid[i + 1][j]
						+ grid[i][j + 1]) * 0.25;

			}
		}

		// update black points
		for (i = 1; i <= grid_size; i++) {
			if (i % 2 == 1)
				j_start = 2;
			else
				j_start = 1;
			for (j = j_start; j <= grid_size; j = j + 2) {
				grid[i][j] = (grid[i - 1][j] + grid[i][j - 1] + grid[i + 1][j]
						+ grid[i][j + 1]) * 0.25;
			}
		}

	}

	// One more update and keep track of max_diff
	max_diff = 0.0;
	// update red points
	for (i = 1; i <= grid_size; i++) {
		if (i % 2 == 1)
			j_start = 1;
		else
			j_start = 2;
		for (j = j_start; j <= grid_size; j = j + 2) {
			old_val = grid[i][j];
			grid[i][j] = (grid[i - 1][j] + grid[i][j - 1] + grid[i + 1][j]
					+ grid[i][j + 1]) * 0.25;

			temp = grid[i][j] - old_val;
			if (temp < 0.0)
				temp = -temp;
			if (temp > max_diff)
				max_diff = temp;
		}
	}

	// update black points
	for (i = 1; i <= grid_size; i++) {
		if (i % 2 == 1)
			j_start = 2;
		else
			j_start = 1;
		for (j = j_start; j <= grid_size; j = j + 2) {
			old_val = grid[i][j];
			grid[i][j] = (grid[i - 1][j] + grid[i][j - 1] + grid[i + 1][j]
					+ grid[i][j + 1]) * 0.25;
			temp = grid[i][j] - old_val;
			if (temp < 0.0)
				temp = -temp;
			if (temp > max_diff)
				max_diff = temp;
		}
	}
	gettimeofday(&timer, NULL);
    end_time = timer.tv_sec + (timer.tv_usec/1000000.0); 

	printf("Maximum diff is: %f\n", max_diff);

    double tt = end_time - start_time;
	printf("Compute time for grid-size(%d), iterations(%d) is: %.3f seconds\n",
			grid_size, num_iters, tt);

	free(vals);
	free(grid);
	exit(1);
}

